package com.klun.matrix;

public class MatrixOne {

    public static int[][] matrixPower(int[][] m, int p){
        int[][] res = new int[m.length][m[0].length];
        // 设置res为单位矩阵，相当于整数中的1
        for (int i = 0; i < res.length; i++) {
            res[i][i] = 1;
        }
        int[][] tmp = m;
        // p 右移一位
        for (; p != 0 ; p>>=1) {
            if((p & 1)!=0){
                res = muliMatrix(res,tmp);
            }
            tmp = muliMatrix(tmp,tmp);
        }
        return res;
    }

    /**
     * 矩阵乘法
     * @param m1
     * @param m2
     * @return
     */
    public static int[][] muliMatrix(int[][] m1,int[][] m2){
        int[][] res =  new int[m1.length][m2.length]; // 两个的纵向长度
        for (int i = 0; i < m2[0].length; i++) { // 横向长度
            for (int j = 0; j < m1.length; j++) { // 纵向长度
                for (int k = 0; k < m2.length; k++) {// 纵向长度
                    res[i][j] += m1[i][k] * m2[k][j];
                }
            }
        }
        return res;
    }

    /**
     * 求解斐波那契数列第n项的值得o(logn)方法
     * @param n
     * @return
     */
    public static int f3(int n){
        if(n < 1){
            return 0;
        }
        if(n == 1 || n ==2){
            return 1;
        }
        int[][] base = {{1,1},{1,0}};
        int[][] res = matrixPower(base,n-2);
        return res[0][0] + res[1][0];
    }

    public static void main(String[] args){
        int p =8;
        p>>=2;
        System.out.println(p);
        int i = f3(900);
        System.out.println(i);
    }
}
